<!DOCTYPE html>
<html lang="en">

<head>
    <meta charset="UTF-8">
    <meta http-equiv="X-UA-Compatible" content="IE=edge">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>Document</title>
</head>

<body>
    <script>
        /**
         * 不同子序列回溯
           输入：s = "rabbbit", t = "rabbit"
           输出：3
            3 种可以从 s 中得到 "rabbit" 的方案。
        */
        /* 
            时间：O(2^(m + n))每个字符都面临挑或者不挑
            空间：O(m+n)注意是加法，最多是m+n，s和t都逐渐缩小到比0少
        */
        // 递归方法: 超时
        var numDistinct = function(s, t) {
            let slen = s.length
            let tlen = t.length
            const helper = (i, j) => {
                // t字符缩小到''，从s中肯定能找到，缩小是什么意思？见下面
                if (j < 0) {
                    return 1
                }
                // s字符缩小到''，从s空字符中肯定找不到
                if (i < 0) {
                    return 0
                }
                // babgbag和bag，匹配最后一位，g和g相等，
                    // 此时可以继续匹配'babgba'和'ba'
                    // 也可以匹配'babgba'和'bag'，这里只有i递减，j没有递减
                if (s[i] === t[j]) {
                    return helper(i - 1, j - 1) + helper(i - 1, j)
                } else {
                    // 如果s[i]和t[j]不相等，就让i减减，继续去和t进行匹配
                    return helper(i - 1, j)
                }
            }
            return helper(slen - 1, tlen - 1)
        };
        // console.log(numDistinct('rabbbit', 'rabbit'));
        console.log(numDistinct('babgbag', 'bag'));
    </script>
</body>

</html>